#include <iostream>
#include <vector>
#include <algorithm>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
using namespace std;
#define __NODE_ALLOCATOR_THREADS true

void (* __malloc_alloc_oom_handler)();

//封装C标准库中的malloc, free 和 realloc
template <int inst>
class __malloc_alloc_template
{
private:
    //oom_malloc用于处理malloc内存分配失败的情况
    static void *oom_malloc(size_t);

    //oom_realloc用于处理realloc内存重新分配失败的情况
    static void *oom_realloc(void *, size_t);

public:
    static void *allocate(size_t n)
    {
        //直接调用malloc进行分配内存
        void *result = malloc(n);

        //如果内存分配失败直接调用oom_malloc处理内存分配失败的情况
        if(result == 0) {
            result = oom_malloc(n);
        }
        return result;
    }

    static void deallocate(void *p, size_t)
    {
        //调用free释放掉内存指针
        free(p);
    }

    //重新分配内存
    static void *reallocate(void *p, size_t, size_t new_sz)
    {
        void * result = realloc(p, new_sz);
        if(result == 0) {
            result = oom_realloc(p, new_sz);
        }
        return result;
    }

    //set_malloc_handler函数
    //通过 set_malloc_handler 允许用户自定义内存分配失败时的处理逻辑。
    static void (* set_malloc_handler(void (*f)()))()
    {
        void (* old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }
};

//对__malloc_alloc_template类中定义的成员函数进行定义
//实现malloc分配内存失败时尝试恢复重新分配内存
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    for(;;) {
        //将__malloc_alloc_oom_handler（内存分配失败处理函数）赋值给my_alloc_handler
        my_malloc_handler = __malloc_alloc_oom_handler;
        
        //如果赋值为0，调用__throw_bad_alloc抛出异常
        if(my_malloc_handler == 0) {
            __throw_bad_alloc;
        }
        
        //调用my_alloc_handler，尝试释放掉一些内存
        (* my_malloc_handler)();
        
        //调用malloc尝试重新分配内存
        result = malloc(n);

        //如果分配成功，返回分配的内存指针
        if(result) 
            return (result);

        //分配失败则持续这个过程，知道分配成功为止
    } 
}

template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) {
            __throw_bad_alloc; 
        }
        (*my_malloc_handler)();
        result = realloc(p, n);
        if (result) return(result);
    }
}

typedef __malloc_alloc_template<0> malloc_alloc;

//实现一个简单的内存分配器的模板类simple_alloc
//主要作用为封装底层内存分配器Alloc，提供类安全的内存分配和释放接口
template <class T, class Alloc>
class simple_alloc
{
public:
    //分配 n 个 T类型对象的内存
    static T*allocate(size_t n)
    {
        return 0 == n ? 0 : (T*) Alloc::allocate(n * sizeof(T));
    }

    static T*allocate()
    {
        return (T*) Alloc::allocate(sizeof (T));
    }

    //释放 n 个 T类型对象的内存
    static void deallocate(T *p, size_t n)
    {
        //如果没有释放成功则调用底层分配器
        if(n != 0) {
            Alloc::deallocate(p, n * sizeof(T));
        }
    }

    static void deallocate(T *p)
    {
        Alloc::deallocate(p, sizeof(T));
    }
};

template <class Alloc>
class debug_alloc 
{
private:
    //在日常分配内存中系统常常多分配一部分给我们用于存储分配的内存大小
    //定义额外分配的内存大小（单位为字节）
    enum {extra = 8};
      
public:
    //分配n个字节的内存
    static void * allocate(size_t n)
    {
        //由于char类型占一个字节内存，方便内存的处理
        char *result = (char *)Alloc::allocate(n + extra);
        *(size_t *)result = n;
        return result + extra;
    }

    //释放指针P指向的内存
    static void deallocate(void *p, size_t n)
    {
        //将指针p向前移动extra，找到实际分配内存的起始地址
        char *real_p = (char*)p - extra;

        //检查前 extra 字节中存储的大小是否与 n 一致（用于调试）
        assert(*(size_t *)real_p == n);

        //调用Alloc中的成员函数deallocate释放内存
        Alloc::deallocate(real_p, n + extra);
    }

    static void *reallocate(void *p, size_t old_sz, size_t new_sz)
    {
        char *real_p = (char*) p - extra;
        assert(*(size_t *)real_p == old_sz);

        //调用底层分配器 Alloc::reallocate 重新分配 old_sz + extra 字节的内存为 new_sz + extra 字节。
        char *result = (char*)Alloc::reallocate(real_p, old_sz + extra, new_sz + extra);
        
        //在新的内存的前 extra 字节中存储新的分配大小 new_sz。
        *(size_t *)result = new_sz;
        return result + extra;

    }
};

enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = _MAX_BYTES / _ALIGN};

//对于alloc关键字进行类模板定义
template <bool threads, int inst>
class _default_alloc_template
{
private:
    //首先将所要开辟的空间进行对齐/补齐
    static size_t ROUND_UP(size_t bytes) 
    {
        //其中_ALIGN为对齐的数值
        //(bytes) + _ALIGN - 1保证最少是下一个对齐值的起点
        //& ~(_ALIGN)为按位与的一个操作将结果向下舍入到最近的_ALIGN的倍数
        return (((bytes) + _ALIGN - 1) & ~(_ALIGN - 1));
    }

    //联合体公用一块内存，联合体的大小为最大成员的大小
    union obj{
        union obj * free_list_link;//指向下一个空闲内存块的指针
        char client_data[1];//一个大小为1的字符串数组，表示客户端实际使用的数据
    };

    //传入的数据变成8整数倍的下标
    //根据传入字节数bytes 计算对应空闲链表的索引
    static  size_t FREELIST_INDEX(size_t bytes) 
    {
        return (((bytes) + _ALIGN - 1) / _ALIGN);
    }

    //refill函数用于在空闲链表中获取一个大小为n的内存块，如果链表为空则调用下面的chunk_alloc函数重新分配新的内存块
    //当客户端请求分配内存的时候，如果对应的链表为空，则会调用refill来补充空闲链表
    static void *refill(size_t n);

    //用于从内存池中分配一块连续的内存，传入n 代表内存传入内存块的大小，nobjs代表内存块的数量
    static char *chunk_alloc(size_t n, int& nobjs);

    //start_free指向内存池中空闲内存的起始地址
    //end_free指向内存池中空闲内存的结束地址
    //heap_size代表内存池的总大小
    static char *start_free;
    static char *end_free;
    static size_t heap_size;

    static obj * volatile free_list[_NFREELISTS];

public:
    //内存分配的核心函数
    //主要用于分配和释放小块的内存，通过free_list来管理内存块，并根据请求的大小
    //决定是否使用自定义分配器或直接调用系统级的内存分配函数
    static void *allocate(size_t n) 
    {
        //定义指向空闲链表的指针，其中_VOLATILE表示这个指针可能被其他线程修改，用来防止被优化
        obj * volatile * my_free_list;

        //指向分配内存块的指针，_RESTRICT表示该指针唯一，不会被其他的指针别名化
        obj * __restrict result;

        //判断请求分配内存的大小是否大于128字节
        //超过128字节则使用malloc_alloc::allocate来分配内存
        if(n > (size_t) _MAX_BYTES) {
            return (malloc_alloc::allocate(n));
        }

        //获取free_list下标对应的地址
        my_free_list = free_list + FREELIST_INDEX(n);
        result = *my_free_list;

        // 当数组的元素内容为NULL时，重新填充
        if (result == 0) {					
            void *r = refill(ROUND_UP(n));
            return r;
        }

        // 将数组的内容变成原数组内容指向下一个空闲地址
        *my_free_list = result -> free_list_link;		
        return (result);
    }

    static void deallocate(void *p, size_t n)
    {
        obj *q = (obj *)p;
        obj * volatile * my_free_list;

        //判断的过程和上面是一致的
        if(n > (size_t) _MAX_BYTES) {
            malloc_alloc::deallocate(p, n);
            return;
        }

        //将释放的内存块插入空闲链表的头部
        my_free_list = free_list + FREELIST_INDEX(n);
        q -> free_list_link = *my_free_list;
        *my_free_list = q;
    }

    static void * reallocate(void *p, size_t old_sz, size_t new_sz);

};

template <bool threads, int inst>
typename _default_alloc_template<threads, inst>::obj * volatile _default_alloc_template<threads, inst>::free_list[_NFREELISTS] = {nullptr};

template <bool threads, int inst>
char * _default_alloc_template<threads, inst>::start_free = nullptr;

template <bool threads, int inst>
char * _default_alloc_template<threads, inst>::end_free = nullptr;

template <bool threads, int inst>
size_t _default_alloc_template<threads, inst>::heap_size = 0;


typedef _default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
typedef _default_alloc_template<false, 0> single_client_alloc;

//size 表示每一个内存块的大小，nobjs表示有n个 内存块
//从内存池中分配一块连续的内存空间
template <bool threads, int inst>
char* _default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
{
    //result 分配的内存块的起始地址
    //total_bytes 所需要分配的总字节数
    //bytes_left 内存池中剩余的字节数
    char* result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;

    //内存池中剩余空间足够
    //如果剩余的内存大于请求的，将start_free往后移动，并返回整块的内存给refill
    if(bytes_left >= total_bytes) {
        result = start_free;
        start_free += total_bytes;
        return (result);
    }

    //内存池剩余的空间不足但是能够分配部分
    // 当不够20个默认的size时,但是剩余的却>=size，所以能分配多少分配多少
    else if(bytes_left >= size) {
        //调整nobjs为实际可以分配的内存块数量
        nobjs = bytes_left / size;

        //更新total_bytes为实际分配的字节数
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return (result);
    }

    //当内存池的剩余空间不足
    else {
        //计算所需要分配的字节数
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
    //如果内存池中还有剩余空间（bytes_left > 0），则将剩余空间插入对应的空闲链表中。
        if (bytes_left > 0) {
            obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);
            
            //将空闲的内存池做头插，放在链表中
            ((obj *)start_free) -> free_list_link = *my_free_list;
            *my_free_list = (obj *)start_free;
        }

        //调用 malloc(bytes_to_get) 分配新内存。
        start_free = (char *)malloc(bytes_to_get);

        //内存池中没有一点剩余空间，已经不能再分配了
        if (0 == start_free) {
            int i;
            obj * volatile * my_free_list, *p;

            // 我们不尝试配置较小的区块，因为在多进程机器上容易造成灾难
            //如果 malloc 失败（start_free == 0），则尝试从空闲链表中回收内存块。
            for (i = size; i <= _MAX_BYTES; i += _ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;

                //如果空闲链表中有可用内存块，则使用该内存块，并递归调用 chunk_alloc
                if (0 != p) {
                    *my_free_list = p -> free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;
                    return(chunk_alloc(size, nobjs));
                }
            }  

            //如果空闲链表中没有可用内存块，
            //则调用 malloc_alloc::allocate(bytes_to_get) 分配内存
            end_free = 0;
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
        }

        //更新内存池状态
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;

        //递归调用 chunk_alloc，重新尝试分配内存。
        return(chunk_alloc(size, nobjs));
    }

}

//返回size n的地址，也可能添加申请多个到free_list中
//refill函数用于在空闲链表中补充内存块。
//它从内存池中分配一块连续的内存，并将其拆分为多个小块，插入到对应的空闲链表中
template <bool threads, int inst>
void* _default_alloc_template<threads, inst>::refill(size_t n)
{
    int nobjs = 20;

    //申请20个size的大小的空间，nobjs是引用
    char *chunk = chunk_alloc(n, nobjs);

    //my_free_list表示指向空闲链表的指针
    //result表示给调用者的内存块
    //current_obj , next_obj 表示遍历和拆分内存块
    obj * volatile * my_free_list;
    obj * result;
    obj * current_obj;
    obj * next_obj;
    int i;

    //如果nobjs 为1，表示内存池中只能分配一个内存块，直接返回chunk不进行拆分
    if(nobjs == 1) {
        return (chunk);
    }

    //free_list表示空闲链表数组，用于管理小块内存

    //根据n 计算对应的空闲链表索引，并获取该空闲链表的地址
    my_free_list = free_list + FREELIST_INDEX(n);

    //chunk大小是整块，需要拆分出来变成多条,并将其插入到空闲链表中
    //将chunk强制转换为obj*类型，赋值给result
    result = (obj*) chunk;

    //将chunk + n 赋值给next_obj，并将其插入到空闲链表中
    *my_free_list = next_obj = (obj*) (chunk + n);

    //通过遍历将chunk拆成多个小块
    //将每个小块插入到空闲链表中，并设置free_list_link指向下一个内存块
    for(i = 1; ; i++) {
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj + n);
        if(nobjs - 1 == i) {
            current_obj->free_list_link = 0;
            break;
        }
        else {
            current_obj->free_list_link = next_obj;
        }
    }
    return (result);
}

//p指向旧内存块的指针
//old_sz表示旧内存块的大小
//new_sz表示新内存块的大小
template <bool threads, int inst>
void* _default_alloc_template<threads, inst>::reallocate(void *p, size_t old_sz, size_t new_sz)
{
    //copy_sz表示需要从旧内存块复制到新内存块的字节数
    void *result;
    size_t copy_sz;

    //大内存块的处理
    //如果旧内存块和新内存快的大小都大于_MAX_BYTES,直接调用realloc重新分配内存
    if(old_sz > (size_t) _MAX_BYTES && new_sz > (size_t) _MAX_BYTES) {
        return (realloc(p, new_sz));
    }

    //大小相同的情况下
    //直接返回旧内存块的指针p，不需要重新分配
    if(ROUND_UP(old_sz) == ROUND_UP(new_sz)) {
        return (p);
    }

    //重新分配内存
    result = allocate(new_sz);

    //复制数据,将旧内存块中的数据复制到新内存块中
    //进行判断复制较大内存块
    copy_sz = new_sz > old_sz ? old_sz : new_sz;
    //将P指向的旧内存块中的数据复制到result指向的新内存块中
    memcpy(result, p, new_sz);

    //释放就内存块
    deallocate(p, old_sz);
    
    return (result);
}                                       

